package 动态规划;

public class 最长上升子序列 {
	
	
	public static void main(String[] args) {
		System.out.println(lis2(new int[]{10, 2, 2, 5, 1, 7, 101, 18}));
	}
	/*
	 * 给定一个无序的整数序列，求出它最长上升子序列的长度（要求严格上升）
	 * 比如 [10, 2, 2, 5, 1, 7, 101, 18] 的最长上升子序列是 [2, 5, 7, 101]、 [2, 5, 7, 18]，长度是 4
	 */
	public static int lis(int[] nums) {
		if (nums == null || nums.length == 0) return 0;
		int[] dp = new int[nums.length];
		int max = dp[0] = 1;
		for (int i = 1; i < dp.length; i++) {
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					dp[i] = Math.max(dp[j], dp[i]);
				}
			}
			dp[i] += 1;
			max = Math.max(dp[i], max);
		}
		return max;
	}
	
	/**
	 * 二分搜索法
	 * 把序列比作扑克牌
	 * 遍历序列, 拿到每一个元素
	 * 从左到右遍历牌堆, 如果牌顶 >= 元素, 则把元素放到牌顶
	 * 遍历到牌堆最后, 没有符合的牌顶, 则新建牌堆
	 * 寻找符合牌顶的过程可以用二分搜索进行优化
	 * 最后牌堆的数量就是最长上升子序列的长度
	 */
	public static int lis2(int[] nums) {
		if (nums == null || nums.length == 0) return 0;
		int[] top = new int[nums.length];	// 牌堆数组
		int len = 0;	// 牌堆数量
		for (int num : nums) {
			int begin = 0;
			int end = len;
			while (begin < end) {
				int mid = (begin + end) >> 1;
				if (num <= top[mid]) {
					end = mid;
				} else {
					begin = mid + 1;
				}
			}
			top[begin] = num;
			if (begin == len) len++;
		}
		return len;
	}
	
}
